Divide and conquer is an Algorithm paradigm which we use to solve the big data problems. As by its name itself divide and conquer, this algorithm divides a huge problem into sub-parts and then try to solve the specific subpart to get the solution. We often use the recursion statements in Divide and Conquer algorithms, the divide and conquer algorithm keep dividing a problem into sub-parts or atomic elements until the program gets solved. Binary search, Merge sorting, etc are the applications of Divide and Conquer algorithm.
Divide and Conquer Stages
The Divide and Conquer Algorithm is divided into 3 stages
- Divide or Break.
- Conquer or Solve.
- Merge or Combine.
Divide or Break
In Divide or Break stage we divide the problem into smaller parts. Here we use the recursive statement to divide the main problem, the recursive statement continues to break the problem until we get an appropriate result or all the elements get broken into atomic value.
Conquer or Solve
When we Divide or Break the problem into small parts at the same time, we try to solve those small problems.
Merge or Combine
Once we have solved the program and we got our result using the sub-parts we need to get merge or combine back all the sub-parts to the original problem.
Some Applications of Divide and Conquer algorithm:
- Merge Sort
- Quick Sort
- Binary Search
- Strassen's Matrix Multiplication
- Closest pair (points)
People are also reading: